//144 Binary Tree Preorder Traversal
/*
不使用递归，实现二叉树的前序遍历

Input:
	1
	 \
	  2
	 /
	3
Output: [1,2,3]

递归的本质是栈调用，可以用栈实现谦虚遍历



*/
vector<int> preorderTraversal(TreeNode *root)
{
	vector<int> ret; //最终返回的结果集

	if (!root)
	{
		return ret;
	}
	stack<TreeNode *> s; //临时存放树结点的栈
	s.push(root);

	//
	while (!s.empty())
	{
		TreeNode *node = s.top();
		s.pop(); // 

		ret.push_back(node->val); //

		//先右后左， 保证左子树先遍历
		if (node->right)
		{
			s.push(node->right); 
		}
		if (node->left)
		{
			s.push(node->left);
		}
	}
	return ret;
}